﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BFlatCompile.Nodes
{
	public class ValueTable
	{
		// TODO: don't calculate the index while parsing, simply hold on to the string itself.
		// Then, before serialization, sort the entries by frequency. This ensures that the most frequently used
		// entries only have a 1-byte lookup value and will result in smaller executable size.

		private List<string> ids = new List<string>();
		private Dictionary<string, int> reverse = new Dictionary<string, int>();
		private Dictionary<string, int> frequency = new Dictionary<string, int>();

		public void Register(string value)
		{
			if (this.reverse.ContainsKey(value))
			{
				++this.frequency[value];
			}
			else
			{
				int index = this.ids.Count;
				this.ids.Add(value);
				this.reverse.Add(value, index);
				this.frequency.Add(value, 1);
			}
		}

		public void SortByFrequency()
		{
			string[] items = this.ids.ToArray();
			MergeSort(items, this.frequency, new List<string>(), new List<string>());
			for (int i = 0; i < items.Length; ++i)
			{
				this.ids[i] = items[i];
				this.reverse[items[i]] = i;
			}
		}

		private static void MergeSort(string[] list, Dictionary<string, int> frequency, List<string> swap1, List<string> swap2)
		{
			if (list.Length < 2)
			{
				return;
			}

			if (list.Length == 2)
			{
				if (frequency[list[0]] < frequency[list[1]])
				{
					string t = list[0];
					list[0] = list[1];
					list[1] = t;
				}
				return;
			}

			int half = list.Length / 2;
			for (int i = 0; i < list.Length; ++i)
			{
				(i < half ? swap1 : swap2).Add(list[i]);
			}
			string[] left = swap1.ToArray();
			string[] right = swap2.ToArray();

			swap1.Clear();
			swap2.Clear();

			MergeSort(left, frequency, swap1, swap2);
			MergeSort(right, frequency, swap1, swap2);

			int targetIndex = 0;
			int leftIndex = 0;
			int rightIndex = 0;

			while (leftIndex < left.Length && rightIndex < right.Length)
			{
				if (frequency[left[leftIndex]] > frequency[right[rightIndex]])
				{
					list[targetIndex++] = left[leftIndex++];
				}
				else
				{
					list[targetIndex++] = right[rightIndex++];
				}
			}

			while (leftIndex < left.Length)
			{
				list[targetIndex++] = left[leftIndex++];
			}

			while (rightIndex < right.Length)
			{
				list[targetIndex++] = right[rightIndex++];
			}
		}

		public bool HasId(string value)
		{
			return this.reverse.ContainsKey(value);
		}

		public int GetId(string value)
		{
			return this.reverse[value];
		}

		public string[] GetIds()
		{
			return this.ids.ToArray();
		}
	}
}
